#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>

typedef struct
{
	int weight;
	int parent;
	int lchild;
	int rchild;
}HNode,*HTree;

void init_tree(HTree  t, const int(* const alph)[2])
{
	assert(t);
	assert(alph);

	int i = 0;
	for (i = 0; i < 26; i++)
	{
		(t + i)->weight = alph[i][1];
		(t + i)->parent = -1;
		(t + i)->lchild = 0;
		(t + i)->rchild = 0;
	}
	for (; i < 51; i++)
	{
		(t + i)->parent = -1;
		(t + i)->lchild = 0;
		(t + i)->rchild = 0;
	}
}

void search(const HTree t,const int length,int* const L, int* const R)
{
	int i = 0;
	int m = 0;
	int n = 0;

	for (i = 0; i < length; i++)
	{
		if (-1 == (t + i)->parent)
		{
			m = i;
			break;
		}
	}
	for (i++ ; i < length; i++)
	{
		if (-1 == (t + i)->parent)
		{
			n = i;
			break;
		}
	}

	for (i++; i < length; i++)
	{
		if ((-1 == (t + i)->parent) && (((t + m)->weight > (t + i)->weight) || ((t + n)->weight > (t + i)->weight)))
		{
			if ((t + m)->weight > (t + n)->weight)
			{
				m = i;
			}
			else
			{
				n = i;
			}
		}
	}
	*L = m;
	*R = n;
}

void creat_Htree(HTree t)
{
	int i = 0;
	int j = 0;
	int L = 0;
	int R = 0;

	for (i = 26; i < 51; i++)
	{
		search(t,i, &L, &R);
		(t + i)->lchild = L;
		(t + i)->rchild = R;
		(t + i)->weight = (t + L)->weight + (t + R)->weight;
		(t + L)->parent = i;
		(t + R)->parent = i;
	}
}

void Hcode(HTree t, char(*code)[27])
{
	char temp[27] = { 0 };
	int i = 0;
	int j = 0;
	int k = 0;
	int x = 0;
	int y = 'a';

	for (i = 0; i < 26; i++)
	{
		k = 26;
		for (j=i;j!=-1;)
		{
			if ((t + (t + j)->parent)->lchild == j)
			{
				temp[k] = '0';
				k--;
			}
			else if ((t + (t + j)->parent)->rchild == j)
			{
				temp[k] = '1';
				k--;
			}
			j = (t + j)->parent;
		}
		
		k++;
		for ( j = 1; k<27; k++, j++)
		{
			*(*(code + x) + j) = temp[k];
		}
		*(*(code + x) + j) = 0;
		*(*(code + x)) = y;
		x++;
		y++;
	}

}

int main()
{
	int alph[26][2] = { 0 };
	char data[100] = { 0 };
	char code[26][27] = { 0 };
	char temp[26] = { 0 };
	int i = 0;
	int j = 0;
	int k = 0;
	
	for (i = 0,j='a'; i < 26; i++,j++)
	{
		alph[i][0] = j;
	}

	do 
	{
		data[i] = getchar();
		i++;
	} while ('\n' != data[i - 1]);

	i -= 1;
	for (j = 0; j < i; j++)
	{
		for (k = 0;k<26; k++)
		{
			if (alph[k][0] == data[j])
			{
				alph[k][1]++;
				break;
			}
		}
	}

	HTree t= new HNode[51];
	init_tree(t, alph);
	creat_Htree(t);
	Hcode(t, code);
	
	for (i = 0; i < 51; i++)
	{
		if (i == 26)
		{
			putchar('\n');
		}
		printf("%-4d %-4d %-4d %-4d %-4d\n",i, (t + i)->weight, (t + i)->parent, (t + i)->lchild, (t + i)->rchild);
	}
	for (i = 0; i < 26; i++)
	{
		printf("%c  ", code[i][0]);
		for (j = 1; 0 != code[i][j]; j++)
		{
			putchar(code[i][j]);
		}
		putchar('\n');
	}
	
}